package org.example.day04;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO+
 * <div>  某业务需要根据终端的IP地址获取该终端归属的城市，可以根据公开的IP地址池信息查询归属城市。地址池格式如下城市名=起始IP,结束IP，起始和结束地址按照英文逗号分隔，多个地址段采用英文分号分隔。 </div> <div>  <br> </div> <div>  比如City1=1.1.1.1,1.1.1.2;City1=1.1.1.11,1.1.1.16;City2=3.3.3.3,4.4.4.4;City3=2.2.2.2,6.6.6.6。 </div> <div>  一个城市可以有多个IP段，比如City1有2个IP段。城市间也可能存在包含关系，如City3的IP<span>段</span>范围包含City2的IP段范围。现在要根据输入的IP列表，返回最佳匹配的城市列表。 </div> <div>  <br> </div> <div>  注：最佳匹配即包含待查询IP且长度最小的IP段，比如例子中3.4.4.4最佳匹配是City2=<span>3.3.3.3,4.4.4.4</span>，5.5.5.5的最佳匹配是City3<span>=2.2.2.2,6.6.6.6</span>。 </div>
 *
 * 某业务需要根据终端的IP地址获取该终端归属的城市，可以根据公开的IP地址池信息查询归属城市。地址池格式如下城市名=起始IP,结束IP，起始和结束地址按照英文逗号分隔，多个地址段采用英文分号分隔。
 *
 * 比如City1=1.1.1.1,1.1.1.2;City1=1.1.1.11,1.1.1.16;City2=3.3.3.3,4.4.4.4;City3=2.2.2.2,6.6.6.6。
 * 一个城市可以有多个IP段，比如City1有2个IP段。城市间也可能存在包含关系，如City3的IP段范围包含City2的IP段范围。现在要根据输入的IP列表，返回最佳匹配的城市列表。
 *
 * 注：最佳匹配即包含待查询IP且长度最小的IP段，比如例子中3.4.4.4最佳匹配是City2=3.3.3.3,4.4.4.4，5.5.5.5的最佳匹配是City3=2.2.2.2,6.6.6.6。
 * @date 2024/3/11 15:22
 */
public class test079 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String cityIpRangesStr = scanner.nextLine().trim();  // 城市IP段列表字符串
        String queryIpsStr = scanner.nextLine().trim();       // 查询的IP列表字符串

        // 解析城市IP范围
        Map<String, List<Range>> cityIpRanges = parseIpRanges(cityIpRangesStr);

        // 查询IP地址，并找到最佳匹配的城市
        List<String> bestMatches = new ArrayList<>();
        for (String ip : queryIpsStr.split(",")) {
            if (!ip.isEmpty()) {
                String bestMatch = findBestMatch(ip, cityIpRanges);
                bestMatches.add(bestMatch != null ? bestMatch : "");
            }
        }

        // 输出结果
        // 如果某个IP没有找到匹配的城市，则对应位置输出为空字符串
        System.out.println(String.join(",", bestMatches));
    }

    /**
     * 解析IP地址范围字符串，并返回城市与IP范围的映射关系。
     *
     * 思路：
     * 1. 分割输入字符串，提取每一个城市及其对应的IP范围。
     * 2. 将IP范围转换为整数形式，方便后续比较。
     * 3. 构造字典，将城市名映射到其对应的IP范围列表。
     *
     * @param ipRangeStr 输入的城市IP段列表字符串
     * @return 一个字典，键为城市名，值为一个列表，列表中的每个元素是一个IP范围的起始和结束地址的整数形式
     */
    public static Map<String, List<Range>> parseIpRanges(String ipRangeStr) {
        Map<String, List<Range>> cityIpRanges = new HashMap<>();
        for (String segment : ipRangeStr.split(";")) {
            if (!segment.isEmpty()) {
                String[] parts = segment.split("=");
                String city = parts[0];
                String[] ips = parts[1].split(",");
                long startInt = ipToLong(ips[0]);
                long endInt = ipToLong(ips[1]);
                Range range = new Range(startInt, endInt);
                if (cityIpRanges.containsKey(city)) {
                    cityIpRanges.get(city).add(range);
                } else {
                    List<Range> ranges = new ArrayList<>();
                    ranges.add(range);
                    cityIpRanges.put(city, ranges);
                }
            }
        }
        return cityIpRanges;
    }

    /**
     * 在IP范围映射中找到最佳匹配的城市。
     *
     * 思路：
     * 1. 将查询的IP地址转换为整数形式。
     * 2. 遍历每个城市的IP范围，查找包含查询IP的范围。
     * 3. 在所有匹配的范围中，选择长度最小的范围作为最佳匹配。
     *
     * @param ip 查询的IP地址
     * @param cityIpRanges 已解析的城市与IP范围的映射关系字典
     * @return 最佳匹配的城市名，如果没有匹配，则返回null
     */
    public static String findBestMatch(String ip, Map<String, List<Range>> cityIpRanges) {
        String bestMatch = null;
        long ipInt = ipToLong(ip);
        long minRangeSize = Long.MAX_VALUE;
        for (Map.Entry<String, List<Range>> entry : cityIpRanges.entrySet()) {
            String city = entry.getKey();
            List<Range> ranges = entry.getValue();
            for (Range range : ranges) {
                if (range.startInt <= ipInt && ipInt <= range.endInt) {
                    long rangeSize = range.endInt - range.startInt;
                    // 更新最佳匹配的城市和范围长度
                    if (rangeSize < minRangeSize) {
                        bestMatch = city;
                        minRangeSize = rangeSize;
                    }
                }
            }
        }
        return bestMatch;
    }

    /**
     * 将IP地址转换为长整型表示。
     *
     * @param ip IP地址字符串
     * @return IP地址的长整型表示
     */
    public static long ipToLong(String ip) {
        String[] parts = ip.split("\\.");
        long result = 0;
        for (String part : parts) {
            result = result * 256 + Integer.parseInt(part);
        }
        return result;
    }

    /**
     * 表示一个IP范围的起始和结束地址。
     */
    static class Range {
        long startInt;
        long endInt;

        public Range(long startInt, long endInt) {
            this.startInt = startInt;
            this.endInt = endInt;
        }
    }
}
